import java.util.Stack;

public class ValidateStackSequences {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int i = 0, n = popped.length;

        for(int x : pushed) {
            // 不断入栈
            stack.push(x);

            // 当 popped 数组 i 下标元素与栈顶元素不同, 则继续入栈
            // 相同则出栈
            while(!stack.isEmpty() && popped[i] == stack.peek()) {
                stack.pop();
                i++;
            }
        }

        // 如果最后栈为空, 则出栈顺序合法, 反之不合法
        return stack.isEmpty();
    }
}
